package bstsetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/13 17:10
 * 选择排序非原地实现:
 * 实现思路： 1：先把数组转换成可变数组
 *          2：找到最小值并且记住最小值的索引，后面需要删除可遍数组中的最小值
 *          3：外层每次循环都从索引0开始
 *          4：定义一个k，赋值的下标索引自增
 *          5：循环完毕就输出排序好的数组
 */
public class mycode1 {

//    选择排序:
//    先把小的拿出来,再把小的拿出来,
//    再从剩余的里面把小的拿出来
//    每次选择还没有处理的元素里面的最小值
//     放到已经排序序列的末尾

     public static int[] selectSort(int[] data){

         //非原地实现
//         1：转换为可变数据
         List<Integer> arraylist = new ArrayList<>();
         for (Integer num : data){
             arraylist.add(num);
         }


            int k = 0;
         while (arraylist.size() !=0){
             int i = 0;
             int minData = arraylist.get(0);
             int minIndex = 0; ;
             for (int j = 1; j < arraylist.size(); j++) {
                 if(arraylist.get(j) < minData){
                     minData =  arraylist.get(j);
                     minIndex = j;
                 }
             }
             data[k++] = arraylist.get(minIndex);
             arraylist.remove(minIndex);

         }
        return data;
     }

    public static void main(String[] args) {
        int[] data1 = {6,4,2,3,1,5};
        int[] data2 = {6,4,2,3,2,1,5,5,};
        int[] sort = mycode1.selectSort(data2);
        for (int n:sort){
            System.out.println(n);
        }
    }
}
